#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<math.h>
#include<vector>
#include<queue>
using namespace std;

class Solution {
public:
    int generateKey(int x, int y, int z) {
        int ret = 0;
        for (int pow10 = 1; x && y && z; pow10 *= 10)
        {
            ret += min({ x % 10,y % 10,z % 10 }) * pow10;
            x /= 10;
            y /= 10;
            z /= 10;
        }
        return ret;
    }

    string stringHash(string s, int k) {
        int n = s.length();
        string ans(n / k, 'a');
        for (int i = 0; i < s.size(); i += k)
        {
            int num = 0;
            for (int j = i; j < k + i; ++j)
            {
                num += s[j] - 'a';
            }
            ans[i / k] += num % 26;
        }
        return ans;
    }

    int busyStudent(vector<int>& begin, vector<int>& end, int qt) {
        int ans = 0;
        for (int i = 0; i < end.size(); ++i)
        {
            if (qt >= begin[i] && qt <= end[i]) ++ans;
        }
        return ans;
    }

    void mold()
    {
        int n, m, q;
        cin >> n >> m >> q;
        vector<vector<int>> vv(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                cin >> vv[i][j];
            }
        }

        vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + vv[i][j] - dp[i - 1][j - 1];
            }
        }

        for (int i = 0; i < q; ++i)
        {
            int x1, x2, y1, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
        }
    }

    bool checkTwoChessboards(string c1, string c2) {
        vector<vector<int>> vv(9, vector<int>(9));
        for (int i = 1; i <= 8; ++i)
        {
            for (int j = 1; j <= 8; ++j)
            {
                if ((i % 2 == 0 && j % 2 != 0) || (i % 2 != 0 && j % 2 == 0)) vv[i][j] = 1;
                else vv[i][j] = 0;
            }
        }
        int x1 = (c1[0] - 'a') + 1, y1 = (c1[1] - '0'), x2 = (c2[0] - 'a') + 1, y2 = (c2[1] - '0');
        if (vv[x1][y1] == vv[x2][y2]) return true;
        return false;
    }

    vector<int> resultsArray(vector<vector<int>>& queries, int k) {
        vector<int> ans(queries.size(), -1);
        priority_queue<int> pq;
        for (int i = 0; i < queries.size(); ++i)
        {
            pq.push(abs(queries[i][0]) + abs(queries[i][1]));
            if (pq.size() > k) pq.pop();
            if (pq.size() == k) ans[i] = pq.top();
        }
        return ans;
    }
};